The disclosure generally relates to branch prediction in a processor, and more particularly, to selecting a predicted indirect branch address. Still more specifically, the disclosure relates to techniques for selecting a predicted indirect branch address from global and local caches.
A branch instruction in an instruction sequence often involves a hazard. A conditional branch instruction in an instruction sequence is even more problematic. In this case, a processor may or may not branch, depending on a calculation that has not yet occurred. Pipelined processors may stall, may attempt branch prediction, or may execute two different program sequences (i.e., execute a first program sequence assuming a branch is ‘taken’ and a second program sequence assuming the branch is ‘not taken’), discarding all work associated with the incorrect program sequence. A pipelined processor with a branch predictor that usually makes correct predictions can minimize the performance penalty associated with branching. However, incorrect predictions create additional processor work, such as flushing instructions corresponding to an incorrect code path from a processor pipeline before executing instructions along a correct code path.
In computer architecture, a branch predictor is usually implemented as a digital circuit that is configured to predict a path taken by a branch instruction (e.g., an if-then-else structure). The purpose of a branch predictor is to improve flow in an instruction pipeline. Branch predictors play a critical role in achieving high effective performance in many modern pipelined processor architectures. Two-way branching is usually implemented with a conditional jump instruction. A conditional jump can either be ‘not taken’ and continue execution with a first code branch that immediately follows a conditional jump or can be ‘taken’ and jump to a different place in program memory where a second code branch is stored. In general, it is uncertain whether a conditional jump will be ‘taken’ or ‘not taken’ until an associated condition has been calculated and the conditional jump has passed an execution stage in an instruction pipeline.
Without branch prediction, a pipelined processor has to wait until the conditional jump instruction passes an execute stage before a next instruction can enter a fetch stage in the pipeline. A branch predictor attempts to avoid the time delay (associated with waiting until the conditional jump instruction passes an execute stage) by predicting whether the conditional jump is most likely to be ‘taken’ or ‘not taken’. Code from the branch that is predicted to be the most likely path is then fetched and speculatively executed. If the predicted code path is later detected to be the wrong code path, then speculatively executed or partially executed instructions are flushed from an instruction pipeline, and the pipeline is refilled with code from the correct branch, incurring a time delay. In general, the time delay attributable to branch misprediction is equal to the number of stages in the pipeline from a fetch stage to an execute stage. Modern processors tend to have relatively long pipelines, and a misprediction time delay is typically between ten to twenty clock cycles. The longer the pipeline, the greater the need for an accurate branch predictor.
Static prediction is the simplest branch prediction technique, as static prediction does not rely on information about a dynamic code execution history. That is, branch predictors employing static prediction predict an outcome of a branch instruction as ‘taken’ or ‘not taken’ based solely on the branch instruction.
Dynamic branch prediction, on the other hand, tracks whether branches are ‘taken’ or ‘not taken’. The first time a conditional jump instruction is encountered there is essentially no information on which to base a prediction. When a branch predictor subsequently encounters a conditional jump instruction that has executed several times, the branch predictor can base a prediction on the branch history. The branch predictor may, for example, recognize that the conditional jump is ‘taken’ more often than ‘not taken’ or that the conditional jump is ‘taken’ every ‘nth’ time.
It should be appreciated that branch prediction is not the same as branch target prediction. Branch prediction (or branch direction prediction) attempts to guess whether a conditional jump will be ‘taken’ or ‘not taken’. Branch target prediction attempts to predict an address (target) of a taken conditional or unconditional jump before the target is computed (i.e., by decoding and executing the taken conditional or unconditional jump (i.e., branch instruction)). Branch prediction and branch target prediction are often combined into the same branch prediction unit.